package com.algorithm.search;

/**
 * @program: study
 * @className: BinarySearch
 * @description: TODO
 * @author: kukuxiahuni
 * @create: 2020-01-12 16:41
 * @version: v1.0
 **/
public class BinarySearch {

    public static void main(String[] args) {
//        int[] array = {8, 11, 19, 23, 27, 33, 45, 55, 67, 98};
        int[] array = {1, 3, 4, 5, 6, 8, 8, 8, 11, 18};

//        System.out.println(search(array, 19));
//        System.out.println(recursiveSearch(array, 19, 0, array.length - 1));
        System.out.println(searchFirstNumber(array, 8));
        System.out.println(searchLastNumber(array, 8));
        System.out.println(searchFirstEGNumber(array, 10));
        System.out.println(searchLastELNumber(array, 10));

    }

    /**
     * 功能描述: 二分查找
     *
     * @param: 1
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/12 4:41 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/12 4:41 下午
     **/
    private final static int search(int[] array, int n) {


        if (array == null) {
            return -1;
        }

        int low = 0, high = array.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (array[mid] == n) {
                return mid;
            } else if (array[mid] > n) {
                //左半区
                high = mid - 1;
            } else {
                low = mid + 1;
            }

        }
        return -1;
    }


    /**
     * 功能描述: 采用递归方式进行二分查找
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/12 4:46 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/12 4:46 下午
     **/
    public final static int recursiveSearch(int[] array, int n, int low, int high) {

        /**
         * 退出条件
         */
        if (low > high) {
            return -1;
        }

        int mid = low + (high - low) / 2;

        if (array[mid] == n) {
            return mid;
        } else if (array[mid] > n) {
            return recursiveSearch(array, n, low, mid - 1);
        } else if (array[mid] < n) {

            return recursiveSearch(array, n, mid + 1, high);
        }

        return -1;

    }

    /**
     * 功能描述: 查找数组中，给定元素出现的第一个值
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/12 5:08 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/12 5:08 下午
     **/
    public final static int searchFirstNumber(int[] array, int n) {

        if (array == null) {
            return -1;
        }

        int low = 0, high = array.length - 1;
        while (low <= high) {
            int mid = low + ((high - low) >>> 1);
            //左半区
            if (array[mid] > n) {
                high = mid - 1;
            } else if (array[mid] < n) {
                //右半区
                low = mid + 1;
            } else {
                //当指针位置元素为n时，需要判定其是不是第一个,如果是，则返回
                if (mid == 0 || array[mid - 1] != n) {
                    return mid;
                }
                //不是第一个，继续在左半区查找
                high = mid - 1;
            }

        }

        return -1;
    }

    /**
     * 功能描述: 查找最后一个值等于给定值的元素
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/12 5:17 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/12 5:17 下午
     **/
    public final static int searchLastNumber(int[] array, int n) {

        if (array == null) {
            return -1;
        }

        int low = 0, high = array.length - 1;

        while (low <= high) {
            int mid = low + ((high - low) >>> 1);

            /**
             * 左半区
             */
            if (array[mid] > n) {
                high = mid - 1;
            } else if (array[mid] < n) {
                /**
                 * 右半区
                 */
                low = mid + 1;
            } else if (array[mid] == n) {
                //相等的时候，需要判定其是不是最后一个元素
                if (mid == array.length - 1 || array[mid + 1] != n) {
                    return mid;
                }

                //不相等的时候,继续向右半区查找
                low = mid + 1;
            }
        }
        return -1;
    }

    /**
     * 功能描述: 查找第一个大于等于给定元素的值
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/12 5:25 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/12 5:25 下午
     **/
    public final static int searchFirstEGNumber(int[] array, int n) {
        if (array == null) {
            return -1;
        }

        int low = 0, high = array.length - 1;

        while (low <= high) {
            int mid = low + ((high - low) >>> 1);

            /**
             * 当中间值>n时，需要判定其是否是第一个
             */
            if (array[mid] >= n) {

                if (mid == 0 || array[mid - 1] < n) {
                    return mid;
                }

                //否则，向左半区查找
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return -1;
    }
    /**
     * 功能描述: 查找最后一个小于等于给定元素的值
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/12 5:25 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/12 5:25 下午
     **/
    public final static int searchLastELNumber(int[] array, int n) {
        if (array == null) {
            return -1;
        }

        int low = 0, high = array.length - 1;

        while (low <= high) {
            int mid = low + ((high - low) >>> 1);

            /**
             * 当中间值>n时，需要判定其是否是第一个
             */
            if (array[mid] > n) {
                high = mid - 1;

            } else if (array[mid] <= n) {
                /**
                 * 判定是否是最后一个元素
                 */
                if (mid == array.length - 1 || array[mid + 1] > n) {
                    return mid;
                }
                low = mid + 1;
            }
        }

        return -1;
    }

}
